package demo1;
import java.util.*;

public class DynamicPlanningPractise {
    /**
     * 最长数对链 -> 由于使用的直接插入排序，时间复杂度太高*/
    public int findLongestChain(int[][] p) {
        //前一个位置的right位置<后一个位置的left位置，可以构造为数对链
        //有一个疑问 数对必定是left+1=right吗 --》不必在乎
        /**
         状态表示：
         dp[i]表示已i下标元素为结尾时，最长数对链的长度
         状态转移方程：
         情况划分：
         情况一：长度为1的数对链，仅由自身组成
         情况二：长度大于1的数对链，此时需要能够构造为数对链，即需要满足p[i][0]>p[j][1]
         在此基础上再求得最长数对链
         初始化：
         每个数对链，其长度最长也为1，故将整个dp表初始化为1 */

        //1 预处理，以第一个位置进行排序，写一个直接插入排序吧 --》插入排序太慢了 搞个快速排序吧
        int n = p.length;
        for(int i = 1; i < n; i++) {
            int left = p[i][0];
            int right = p[i][1];
            int j = i-1;
            while(j>=0) {
                if(left<p[j][0]) {
                    p[j+1][0] = p[j][0];
                    p[j+1][1] = p[j][1];
                    j--;
                } else {
                    break;
                }
            }
            p[j+1][0] = left;
            p[j+1][1] = right;
        }
        //2 创建dp表
        int[] dp = new int[n];
        //3 初始化
        Arrays.fill(dp,1);
        //4 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                dp[i] = p[i][0]>p[j][1] ? Math.max(dp[i],dp[j]+1) : dp[i];
                ret = Math.max(dp[i],ret);
            }
        }
        //5 返回值
        return ret;
    }

    /**
     * 最长数对链 -使用快排进行优化
     * */
    public int findLongestChainOther(int[][] p) {
        //前一个位置的right位置<后一个位置的left位置，可以构造为数对链
        //有一个疑问 数对必定是left+1=right吗 --》不必在乎
        /**
         状态表示：
         dp[i]表示已i下标元素为结尾时，最长数对链的长度
         状态转移方程：
         情况划分：
         情况一：长度为1的数对链，仅由自身组成
         情况二：长度大于1的数对链，此时需要能够构造为数对链，即需要满足p[i][0]>p[j][1]
         在此基础上再求得最长数对链
         初始化：
         每个数对链，其长度最长也为1，故将整个dp表初始化为1 */

        //1 预处理，快速排序
        int n = p.length;
        quickSort(p,0,n-1);
        //2 创建dp表
        int[] dp = new int[n];
        //3 初始化
        Arrays.fill(dp,1);
        //4 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                dp[i] = p[i][0]>p[j][1] ? Math.max(dp[i],dp[j]+1) : dp[i];
                ret = Math.max(dp[i],ret);
            }
        }
        //5 返回值
        return ret;
    }
    /**快速排序 */
    private void quickSort(int[][] array, int left, int right) {
        if(left>=right) return;
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }
    private int partition(int[][] array, int left, int right) {
        int index = left;//以最左边的数为基准值
        int num = array[index][0];
        while(left<right) {
            while(left<right && array[right][0]>=num) {
                right--;
            }
            while(left<right && array[left][0]<=num) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,index,left);
        return left;
    }
    private void swap(int[][] array,int o1,int o2) {
        int tmpLeft = array[o1][0], tmpRight = array[o1][1];
        array[o1][0] = array[o2][0];
        array[o1][1] = array[o2][1];
        array[o2][0] = tmpLeft;
        array[o2][1] = tmpRight;
    }

    /**
     * 求最长等差子序列
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int longestSubsequence(int[] arr, int difference) {
        /**
         有思路 - 先做 再写步骤 不然很耗费时间

         目前遇见的问题：
         时间复杂度太高，导致题目超时，应当将时间复杂度降低至O（n）*/
        //将已处理的值存入HashMap中
        int n = arr.length;
        Map<Integer,Integer> map = new HashMap<>();
        //1 创建dp表 - 表示以i位置下标元素为结尾的所有子序列中，最长定差子序列的长度
        int[] dp = new int[n];
        //2 初始化 - 每个元素都可以看作是一个等差子序列 不过长度为1
        map.put(arr[0],1);
        //3 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            if(map.containsKey(arr[i]-difference)) {
                dp[i] = map.get(arr[i]-difference)+1;
            } else{
                dp[i] = 1;
            }
            map.put(arr[i],dp[i]);
        }
        //4 返回值
        return ret;
    }

    /**
     * 最长的斐波那契数列的长度
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）
     * 还未进行优化*/
    public int lenLongestFibSubseq(int[] arr) {
        /**
         如果只设定一个状态表示方法的话，即dp[i]表示以i位置元素为结尾时，所有子序列中，最长的斐波那契子序列的长度
         那么由于其仅仅只表示长度，并且一个斐波那契子序列需要由三个元素组成，故我们无法通过前面的dp值更新后面的dp值

         状态表示：
         因为一个斐波那契子序列需要由三个元素组成，并且其具有a+b=c这样的关系，
         故通过两个值便可以唯一确定一个斐波那契子序列
         因此，我们创建一个n*n的二维dp表，并以两个位置为结尾表示长度，如下
         dp[i][j] 表示以i下标元素和j下标元素为结尾的所有子序列中，最长的斐波那契子序列的长度（i<j）
         状态转移方程：
         由于通过两个值便可以唯一的确定前一个值，故得arr[j]-arr[i] = arr[k](前一个值)
         此时会存在三种情况：
         一：arr[k]不存在，此时他们的最大长度为2
         二：arr[k]这个值位于 arr[i] arr[j]之间，此时也不符合，因为状态表示规定ij为最后两个值
         三：arr[k]存在，那么dp[i][j] = dp[k][i]+1,此时的主要问题是如何找到k下标，
         做法一是遍历数组，找到这个值的下标
         做法二是在解题前先将本数组中的所有元素与下标绑定，存进HashMap中（因为是严格递增，故数组中没有相同的元素）
         初始化：
         整体初始化为最差情况2
         */
        int n  = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++)
            map.put(arr[i],i);
        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化
        Arrays.fill(dp,1);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dp[i][j]=2;
        //3 填表
        int ret = 2;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map.containsKey(arr[j]-arr[i])) {
                    int k = map.get(arr[j]-arr[i]);
                    dp[i][j] = k<i ? dp[k][i]+1 : 2;
                }
                ret = Math.max(ret,dp[i][j]);
            }
        }
        //4 返回值
        return ret<3 ? 0 : ret;
    }
}
